The present invention relates to the field of computer graphics, and in particular to methods and apparatus for analyzing and filtering of still images, video, and other one-dimensional, two-dimensional, three-dimensional, four-dimensional, and higher-dimensional data sets to produce visual effects.
An image histogram specifies the distribution or quantity of colors, tones, intensities, or other scalar, vector, or tuple pixel values in still images or video. An image histogram specifies the number of pixels in an image having a specific color, tone, intensity, or other attribute value, or falling within a specific range of color, tone, intensity, or other attribute values.
Local image histograms contain a great deal of information useful for applications in computer graphics, computer vision and computational photography. A local image histogram specifies the distribution or quantity of values within a specific portion of an image or video, such as within a given distance from a specified pixel, referred to as a pixel's neighborhood. Typically, each pixel in an image may its own local histogram, because each pixel includes a different set of pixels in its respective neighborhood.
Local image histograms contain a great deal of information useful for applications in computer graphics, computer vision and computational photography. Local histograms often show multiple peaks or modes, due to the presence of different surfaces. Separating out the properties of these modes enables sophisticated non-linear image transformations including noise reduction, edge-preserving smoothing, segmentation and stylization.
However, prior techniques for determining a local histogram are computationally difficult and expensive. One prior approach to computing a local histogram is to determine the distribution of pixel values in the neighborhood surrounding a target pixel. However, this approach is computationally expensive for large neighborhoods. For square or rectangular neighborhoods, histogram computations can be accelerated by exploiting the overlap of neighborhoods for adjacent pixels. Unfortunately, square or rectangular neighborhoods have poor signal-processing characteristics and often exhibit clear visual artifacts due to anisotropy.
Moreover, once local histograms around one or more pixels are explicitly determined, many histogram-based operations are nonlinear. This prevents traditional acceleration techniques for large linear filters from being used, further increasing the overall computational expense.
Rather than explicitly determine local histograms around one or more pixels, other prior histogram techniques operate on the histogram indirectly. These prior techniques do not calculate a local histogram for a given pixel. Instead, they attempt to determine or estimate a particular property of attribute of the local histogram. For example, a prior mean-shift technique can identify the nearest local histogram mode, which is the nearest local histogram peak, for a given pixel without directly determining the local histogram for this pixel's neighborhood. However, prior techniques like the mean-shift technique are iterative and require multiple processing passes over the data set before converging to a solution. This increases the required time and computational expense. Moreover, these prior iterative techniques only identify the nearest local histogram mode or nearest local histogram peak. However, there are many applications that would benefit from knowledge of other local histogram modes. Unfortunately, these prior iterative techniques do nothing to identify any other local histogram modes.